import random
class BinTreeNode:
    def __init__(self,data) :
        self.data=data
        self.lchild=None#左孩子
        self.rchild=None#右孩子
        self.parent=None
class BST:
    def __init__(self,data=None) :
        self.root=None
        if data:
            for val in data:
                self.insert_no_res(val)
    #插入(递归)
    def insert(self,node,val):
        if not node:
            node=BinTreeNode(val)
        elif val<node.data:
            node.lchild=self.insert(node.lchild,val)
            node.lchild.parent=node #双向列表
        elif val>node.data:
            node.rchild=self.insert(node.rchild,val)
            node.rchild.parent=node
        return node
    #非递归
    def insert_no_res(self,val):
        p=self.root
        if not p:           #空树
            self.root=BinTreeNode(val)
            return
        while True:
            if val<p.data:
                if p.lchild:
                    p=p.lchild
                else:           #左孩子不存在
                    p.lchild=BinTreeNode(val)
                    p.lchild.parent=p
                    return
            elif val>p.data:
                if p.rchild:
                    p=p.rchild
                else:           #右孩子不存在
                    p.rchild=BinTreeNode(val)
                    p.rchild.parent=p
                    return
            else:
                return
    #查询(递归)
    def query(self,node,val):
        if not node:
            return None
        if node.data<val:
            return self.query(node.rchild,val)
        elif node.data>val:
            return self.query(node.lchild,val)
        else:
            return node
    #非递归查询
    def quert_no_res(self,val):
        p=self.root
        while p:
            if p.data<val:
                p=p.rchild
            elif p.data>val:
                p=p.lchild
            else:
                return p
        return None
    #前序遍历
    def pre_order(self,root):
            if root:
                print(root.data,end=",")#先根节点
                self.pre_order(root.lchild)#再左子树
                self.pre_order(root.rchild)#后右子树
    #中序遍历
    def in_order(self,root):
        if root:
            self.in_order(root.lchild)#先左子树
            print(root.data,end=".")#再根节点
            self.in_order(root.rchild)#后右子树
    #后序遍历
    def post_order(self,root):
        if root:
            self.post_order(root.lchild)#先左子树
            self.post_order(root.rchild)#后右子树
            print(root.data,end=",")#后根节点
    #删除
    def __remove_node_1(self,node):
        #情况一：node是叶子节点
        if not node.parent:
            self.root=None
        if node==node.parent.lchild:#node是它的父亲的左孩子
            node.parnet.lchild=None
            #node.parent=None
        else:#右孩子
            node.parent.rchild=None
    def __remove_node_21(self,node):
        #情况二node只有一个孩子(左孩子)
        if not node.parent:#根节点
            self.root=node.lchild
            node.lchild.parnet=None
        elif node==node.parent.lchild:#它是它父亲的左孩子
                node.parent.lchild=node.lchild
                node.lchild.parent=node.parent
        else:
            node.parent.rchild=node.lchild
            node.lchild.parent=node.parent
    def __remove_node_22(self,node):
        #情况二node只有一个孩子(右孩子)
        if not node.parent:#如果是根节点
            self.root=node.rchild
            node.rchild.parent=None
        elif node==node.parent.lchild:#它是它父亲的左孩子
            node.parent.lchild=node.rchild
            node.rchild.parent=node.parent
        else:
            node.parent.rchild=node.rchild
            node.rchild.parent=node.parent

    
    def delete(self,val):
           if self.root:#不是空树
               node=self.quert_no_res(val)
               if not node:#不存在
                   return False
               if not node.lchild and not node.rchild:#叶子节点
                   self.__remove_node_1(node)
               elif not node.rchild:#2.1只有一个左孩子
                   self.__remove_node_21(node)
               elif not node.lchild:#2.2只有一个右孩子
                   self.__remove_node_22(node)
               else:    #两个孩子都有
                    min_node=node.rchild
                    while min_node.lchild:
                        min_node=min_node.lchild
                    node.data=min_node.data
                    #删除min_node
                    if min_node.rchild:
                        self.__remove_node_22(min_node)
                    else:
                        self.__remove_node_1(min_node)


if __name__=="__main__":
    '''li=list(range(0,100,2))
    random.shuffle(li)
    tree=BST([4,6,7,9,2,1,3,5,8])'''
    tree1=BST([1,4,2,5,3,8,6,9,7])
    #tree=BST(li)
    '''tree.pre_order(tree.root)
    print("")
    tree.in_order(tree.root)
    print("")
    tree.post_order(tree.root)'''
    #print(tree.quert_no_res(4))
    print(tree1.query(tree1.root,4).data)
    tree1.in_order(tree1.root)
    print("")
    tree1.delete(4)
    tree1.in_order(tree1.root)

  

    